<template>
  <ExamPaper
    :items="paper"
    :name="title"
    @update:answers="val => (finalAnswers = val)"
  />
</template>

<script setup>
import { ref, onMounted, computed } from 'vue'
import ExamPaper from '@/components/ExamPaper.vue'
// 使用路由meta中的name作为标题
import { useRoute } from 'vue-router'
const route = useRoute()
const title =  computed(() => {
  return route.meta.title  || '算法题库'
})

const paper = ref([
  {
    question:
    `
    深度优先搜索DFS(树)
    508. 出现次数最多的子树元素和
    中等
    相关标签
    premium lock icon
    相关企业
    给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

    一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

    

    示例 1：



    输入: root = [5,2,-3]
    输出: [2,-3,4]
    示例 2：



    输入: root = [5,2,-5]
    输出: [2]

    /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
    `,
    answer:
    `
    function deal1(root){
      const map = new Map();
      function dfs(node){
        const left = node.left&&node.left.val||0;
        const right = node.right&&node.right.val||0;
        const sum = left+right+node.val;
        
        map.has(sum)?map.set(sum,map.get(sum)+1):map.set(sum,1)
        node.left&&dfs(node.left)
        node.right&&dfs(node.right)
      }
      dfs(root)
      const max = 0;
      let result = [];
      for(const [key,num] of map){
        if(num>max){
          result = [key];
          max = num;
        }else if(num === max){
          result.push(key)
        }else{
          continue
        }
      }
      console.log(result)
      return result;
    }
    `,
    remark:
    `
    `,
  },
  {
    question:
    `
    广度优先搜索BFS(树)
    429. N 叉树的层序遍历
    中等
    相关标签
    premium lock icon
    相关企业
    给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

    树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

    

    示例 1：



    输入：root = [1,null,3,2,4,null,5,6]
    输出：[[1],[3,2,4],[5,6]]
    示例 2：



    输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
    `,
    answer:
    `
    function deal2(root){
      const deepsArr = [];
      function bfs(node,deep = 0){
        deepsArr[deep]?deepsArr[deep].push(node):deepsArr[deep] = [node];
        node.children&&node.children.forEach(element => {
          bfs(element,deep+1)
        });
      }
      bfs(root)
      console.log(deepsArr)
      return deepsArr
    }
    `,
    remark:
    `
    `
  },
  {
    question: `
    栈（难）
    84. 柱状图中最大的矩形
    困难
    相关标签
    premium lock icon
    相关企业
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

    求在该柱状图中，能够勾勒出来的矩形的最大面积。

    

    示例 1:
    <img src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg">


    输入：heights = [2,1,5,6,2,3]
    输出：10
    解释：最大的矩形为图中红色区域，面积为 10
    示例 2：
    <img src="https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg">


    输入： heights = [2,4]
    输出： 4
 
    `,
    answer: `
    function deal3(heights){
      const copyHeights = [...heights];
      const allArea = [];
      copyHeights.sort((a,b)=>a-b);
      const max = copyHeights[heights.length-1];
      const min = copyHeights[0];
      // 大的排前面小的排后面，避免二次排序
      function addToAllArea (area){
        if(!area) return;
        if(allArea.length){
          allArea[0]>area?allArea.push(area):allArea.unshift(area)
        }else{
          allArea.unshift(area)
        }
      }
      for(let i = min; i<=max;i++ ){
        if(i===0){
          continue
        }
        let area = 0;
        heights.forEach((h,index)=>{
          if(h>=i){
            area+=i
            if(index === heights.length-1){
              console.log(i,area,index,'h-i',h,i)
              addToAllArea(area)
            }
          }else{
            console.log(i,area,index,'h-i',h,i)
            addToAllArea(area)
            area = 0;
          }
        })
      }
      console.log(allArea[0],allArea)
      return allArea[0];
    }
    `,
    remark: `
    记得别改传入数组的原始数据，sort会更改原始数组
    `
  }
])
function deal1(root){
  const map = new Map();
  function dfs(node){
    const left = node.left&&node.left.val||0;
    const right = node.right&&node.right.val||0;
    const sum = left+right+node.val;
    
    map.has(sum)?map.set(sum,map.get(sum)+1):map.set(sum,1)
    node.left&&dfs(node.left)
    node.right&&dfs(node.right)
  }
  dfs(root)
  let max = 0;
  let result = [];
  for(const [key,num] of map){
    if(num>max){
      result = [key];
      max = num;
    }else if(num === max){
      result.push(key)
    }else{
      continue
    }
  }
  console.log(result)
  return result;
}
function deal2(root){
  const deepsArr = [];
  function bfs(node,deep = 0){
    deepsArr[deep]?deepsArr[deep].push(node):deepsArr[deep] = [node];
    node.children&&node.children.forEach(element => {
      bfs(element,deep+1)
    });
  }
  bfs(root)
  console.log(deepsArr)
  return deepsArr
}
function deal3(heights){
  const copyHeights = [...heights];
  const allArea = [];
  copyHeights.sort((a,b)=>a-b);
  const max = copyHeights[heights.length-1];
  const min = copyHeights[0];
  // 大的排前面小的排后面，避免二次排序
  function addToAllArea (area){
    if(!area) return;
    if(allArea.length){
      allArea[0]>area?allArea.push(area):allArea.unshift(area)
    }else{
      allArea.unshift(area)
    }
  }
  for(let i = min; i<=max;i++ ){
    if(i===0){
      continue
    }
    let area = 0;
    heights.forEach((h,index)=>{
      if(h>=i){
        area+=i
        if(index === heights.length-1){
          console.log(i,area,index,'h-i',h,i)
          addToAllArea(area)
        }
      }else{
        console.log(i,area,index,'h-i',h,i)
        addToAllArea(area)
        area = 0;
      }
    })
  }
  console.log(allArea[0],allArea)
  return allArea[0];
}
onMounted(()=>{
    deal1({
      val:5,
      left: {
        val:2,
        left: null,
        right: null
      },
      right: {
        val:-3,
        left: null,
        right: null
      }
    })

    deal2({
      val:1,
      children: [
        {
          val:3,
          children: [
            {val:5, children: []},
            {val:6, children: []}
          ]
        },
        {val:2, children: []},
        {val:4, children: []}
      ]
    }) 

    deal3([2,1,5,6,2,3])
})


const finalAnswers = ref([])   // 实时收集到的答案
</script>